/*
Problem: Anagrams
Difficulty: easy
Source:  http://www.leetcode.com/onlinejudge
Notes:
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
*/
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

class Solution {
public:
     vector<string> anagrams(vector<string> &strs) {
     	vector<string> result;
     	map<string, pair<string, bool> > str_hash;

     	for (int i = 0; i < strs.size(); i++) {
     		string temp_str = strs[i];
     		sort(temp_str.begin(), temp_str.end());

     		map<string, pair<string, bool> >::iterator find = str_hash.find(temp_str); 
     		if (find == str_hash.end()) {
     			str_hash.insert(make_pair(temp_str, make_pair(strs[i], false)));
     		} else {
     			if (!find->second.second) {
     				result.push_back(find->second.first);
     				find->second.second = true;
     			}
     			result.push_back(strs[i]);
     		}
     	} 
     	return result;
     }
 };

int main(int argc, char* argv[])
{
	Solution s;

	string strs[] = {"abc", "aba", "bca", "cab", "cc", "baa"};
	vector<string> input;
	for (int i = 0; i < 6; i++)
		input.push_back(strs[i]);

	vector<string> result = s.anagrams(input);
	for (int i = 0; i < result.size(); i++)
		cout << result[i] << endl;
	return 0;
}